import java.util.ArrayList;
import java.util.List;

public class BinaryTree {

    static class TreeNode{

        public char val;
        public TreeNode left; //存储左孩子的引用
        public TreeNode right; //存储右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        //对于没赋值的节点，如D节点，默认为null

        return A; //返回这棵二叉树的头节点
    }

    // 前序遍历
    public void preOrder(TreeNode root){
        if (root==null)return;
        System.out.print(root.val+ " ");
        preOrder(root.left);
        preOrder(root.right);

    }

    //递归前序遍历
    List<Character> list=new ArrayList<>();
    public List<Character> preorderTraversal(TreeNode root) {

        if (root==null)return list;
        //System.out.print(root.val+ " ");
        list.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
        return list;
    }

    public List<Character> preorderTraversa2(TreeNode root) {

       List<Character> list1=new ArrayList<>();
       if (root==null)return list1;
       list1.add(root.val);

       List<Character> leftTree=preorderTraversa2(root.left);
       list1.addAll(leftTree);

        List<Character> rightTree=preorderTraversa2(root.right);
        list1.addAll(rightTree);

        return list1;
    }
    // 中序遍历
    public void inOrder(TreeNode root){
        if (root==null)return;
        inOrder(root.left);
        System.out.print(root.val+ " ");
        inOrder(root.right);
    }

    // 后序遍历
    public void postOrder(TreeNode root){
        if (root==null)return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+ " ");

    }

    // 获取树中节点的个数
    public static int nodeSize;
    public void size1(TreeNode root){
        if (root==null)return ;
        nodeSize++;
        size(root.left);
        size(root.right);
    }

    public int size(TreeNode root){
        if (root==null)return 0;
        return size(root.left)+size(root.right)+1;
    }

    // 获取叶子节点的个数
    public int getLeafNodeCount(TreeNode root){
        if (root==null)return 0;
        if (root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)
                +getLeafNodeCount(root.right);
    }

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if (root==null)return 0;
        if (k==1)return 1;

        return getKLevelNodeCount(root.left,k-1)
        +getKLevelNodeCount(root.right,k-1);
    }

    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if (root==null)return 0;
        int leftTreeHeight=getHeight(root.left);
        int rightTreeHeight=getHeight(root.right);
        return Math.max(leftTreeHeight,rightTreeHeight)+1;
    }


}
